/*******************************************************************
 *
 * 树是一种非线性的数据结构,以分层的方式 存储数据。
 * 树被用来存储具有层级关系的数据,比如文件系统中的文件;树还被用来存储 有序列表。
 *
 * 二叉树是一种特殊的树,它的子节点个数不超过两个。
 * 二叉树具有一些特殊的计算性质,使得在它们之上的一些操作异常高效
 *
 * BST 的一个用途是记录一组数据集中数据出现的次数。
 */

(function () {
    function Node(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.show = show;
    }

    function show() {
        return this.data;
    }

    function BST() {
        this.root = null;
        this.insert = insert;
        this.inOrder = inOrder;
    }

    function insert(data) {
        var n = new Node(data, null, null);
        if (this.root == null) {
            this.root = n;
        } else {
            var current = this.root;
            var parent;
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.left;
                    if (current == null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    }

    function inOrder(node) {
        if (!(node == null)) {
            inOrder(node.left);
            print(node.show() + " ");
            inOrder(node.right);
        }
    }

    function preOrder(node) {
        if (!(node == null)) {
            print(node.show() + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    function postOrder(node) {
        if (!(node == null)) {
            postOrder(node.left);
            postOrder(node.right);
            print(node.show() + " ");
        }
    }

    function getMin() {
        var current = this.root;
        while (!(current.left == null)) {
            current = current.left;
        }
        return current.data;
    }

    function getMax() {
        var current = this.root;
        while (!(current.right == null)) {
            current = current.right;
        }
        return current.data;
    }

    function find(data) {
        var current = this.root;
        while (current != null) {
            if (current.data == data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }

    function remove(data) {
        root = removeNode(this.root, data);
    }

    function removeNode(node, data) {
        if (node == null) {
            return null;
        }
        if (data == node.data) {
            // 没有子节点的节点
            if (node.left == null && node.right == null) {
                return null;
            }
            // 没有左子节点的节点
            if (node.left == null) {
                return node.right;
            }
            // 没有右子节点的节点
            if (node.right == null) {
                return node.left;
            }
            // 有两个子节点的节点
            var tempNode = getSmallest(node.right);
            node.data = tempNode.data;
            node.right = removeNode(node.right, tempNode.data);
            return node;
        } else if (data < node.data) {
            node.left = removeNode(node.left, data);
            return node;
        } else {
            node.right = removeNode(node.right, data);
            return node;
        }
    }

    var nums = new BST();
    nums.insert(23);
    nums.insert(45);
    nums.insert(16);
    nums.insert(37);
    nums.insert(3);
    nums.insert(99);
    nums.insert(22);
    print("Inorder traversal: ");
    inOrder(nums.root);


    print("Preorder traversal: ");
    preOrder(nums.root);

    print("Postorder traversal: ");
    postOrder(nums.root);
}());

function print(x) {
    console.log(x);
}